import java.util.Arrays;

/**
 * 冒泡排序
 * 实现思路：
 * 1.每一轮循环，都将 待排序区间 的最大数字移动到数组靠后的位置
 * 2.移动过程中，较大元素需要与较小元素两两交换位置，
 *   即较小元素逐渐靠前，较大元素逐渐靠后
 *
 * 优点：代码容易实现，思路易掌握
 * 缺点：时间复杂度较高，平均为：O(n^2)
 */
public class BubbleSort {
    public static int[] bubbleSort(int[] nums) {
        int len = nums.length;
        int[] res = Arrays.copyOf(nums, len);
        for (int i = 1; i < len; i++) {
            boolean flag = true;
            // 每一次，将 [0, len - i) 中的最大元素，冒泡到 len - i 索引上
            for (int j = 0; j < len - i; j++) {
                if (res[j] > res[j + 1]) {
                    flag = false;
                    // 移动时，较大元素与后面的较小元素交换位置
                    int temp = res[j];
                    res[j] = res[j + 1];
                    res[j + 1] = temp;
                }
            }
            if (flag) {
                // 第 i 轮的冒泡中，没有元素进行交换，说明数组 nums 已然有序，完成排序
                System.out.println(">>>>>第 " + i + " 轮比较后，完成排序");
                break;
            }
            System.out.println(">>>>>第 " + i + " 轮冒泡后，数组元素为："
                    + Arrays.toString(res));
        }
        return res;
    }
}
